package chapter01;

import java.util.HashMap;
import java.util.Stack;

public class LongestValidParentheses {
    //暴力 O(N^3)
    HashMap<Character,Character> hashMap;
    Stack<Character> stack;

    public boolean valid(int i,int j,String s){
        stack.clear();
        for(i=i;i<=j;i++){
            char c=s.charAt(i);
            if(hashMap.containsKey(c)){
                stack.push(c);
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    if(c!=hashMap.get(stack.pop())){
                        return false;
                    }
                }
            }
        }
        return stack.size()==0;
    }

    public int longestValidParentheses(String s) {
        if(s==null||s.length()<1){
            return 0;
        }
        hashMap=new HashMap<>();
        stack=new Stack<>();
        int length=s.length();
        int len=0;
        hashMap.put('(',')');
        for(int i=0;i<length;i++){
            for(int j=length-1;j>i;j--){
                if((j-i+1)%2==0){
                    if(valid(i,j,s)){
                        len=j-i+1>len?j-i+1:len;
                    }
                }
            }
        }
        return len;
    }

    //动态规划 dp[i] 以下标为i的字符结尾(包括下标i)的最长有效子字符串的长度。
    /**
     * ....(   以'('结尾不匹配 因为都是()成对出现
     * ....)   分为两种情况
     *         1）s[i-1]=='('
     *            ......() dp[i]=dp[i-2]+2
     *         2)s[i-1]==')' && s[i-dp[i-1]-1]=='('
     *            ..((.....)) dp[i]=d[i-1]+2+dp[i-dp[i-1]-2]
     */
    public int longestValidParentheses1(String s) {
        if(s==null||s.length()<1){
            return 0;
        }
        int length=s.length(),max=0;
        int[] dp=new int[length];
        for(int i=1;i<length;i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }else if(i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+2+((i-dp[i-1]-1)>0?dp[i-dp[i-1]-2]:0);
                }
                max=Math.max(max,dp[i]);
            }
        }
        return max;
    }

    //栈
    /**
     * 因为要计算长度 栈中存放下标 为了方便计算排除是s[0]==')'出现空栈 初始化存入-1 代表下一次匹配有效长度是从0开始
     * 1)如果当前s[i]=='('
     *   当前下标i入栈
     * 2)如果当前s[i]==')'
     *   先出栈 表明与当前')'已匹配
     *   a.如果此时栈不空
     *      length=i-stack.peek() 此时栈顶元素表明这次匹配是从stack.peek()+1开始
     *      更新max=max(max,length)
     *   b.如果栈为空
     *      当前下标i入栈 表明之后匹配是从下标i+1开始
     */
    public int longestValidParentheses2(String s) {
        if(s==null||s.length()<1){
            return 0;
        }
        int length=s.length(),max=0;
        Stack<Integer> stack=new Stack<>();
        stack.push(-1);
        for(int i=0;i<length;i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    max=Math.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }

}
